package com.daaij.seventhchapter;

import com.algorithm.NewSortTest;
import com.daaij.sixthchapter.BinaryHeap;

import java.util.*;

public class Sort {

    //comparator，
    //
    // compare方法如果大于0，则认为a1比a2大，把a1放后面。
    //排序这个问题，其实就是针对任意两个数，哪个数排在前，哪个数排在后的问题。推广到所有的  类，那就是 一种抽象数据结构的两个对象，他们的排队规则是什么。
    //由于每个抽象数据结构的判定方式都是不同的，所以需要一个中间层，把判定方式表示为统一的方式。
    //判定方式包含两个部分，一个是比较依据，定义了数据结构中的哪些字段用以比较，这些比较会产生一个比较值。
    //另一个是比较顺序规则，他定义了比较值较高的那个数是排在前面还是排在后面，并最终给出一个比较最终值。
    //底层只能写死比较最终值较高时，第一个比较对象会被排前或者后，最终比较值较低时，第一个比较对象会被排在后或者前。
    //所以在指定规则时，    要指定想要的比较顺序规则与底层写死的最终比较值的规则的映射。

    /**
     * 第一部分、基于比较的排序相关的定理
     *
     * 定理一：N个互异数的数组的平均逆序数为N(N-1)/4
     * N个互异数的序偶组合数为（N-1）N/2，显然正序偶和逆序偶的发生几率应该是相同的，所以平均逆序数为N(N-1)/4
     *
     * 定理二：通过交换相邻元素进行排序的任何算法平均都需要N方的时间。
     * 由于N个互异数平均逆序为N(N-1)/4，而交换相邻元素又只能更改一个逆序（因为交换相邻元素并不能影响除这两个元素外的元素的相对位置，比如，如果交换一个很远的位置，就有可能使得中途
     * 某些元素的逆序得到交换）
     * ，因此平均访问的界是N方。
     *
     *
     *
     */

    //1. 冒泡排序
    public static <T>void bubbleSort(List<T> input, Comparator<T> comparator){

        for(int i = 0; i < input.size();i ++){
            for(int j = 0;j < input.size() - i - 1;j ++){
                if(comparator.compare(input.get(j),input.get(j + 1)) > 0){
                    Collections.swap(input,j,j + 1);
                }
            }
        }
    }

    //2. 选择排序
    public static <T>void selectSort(List<T> input, Comparator<T> comparator){

        for(int i = 0; i < input.size(); i ++){

            T swapTarget = input.get(0);
            int swapIndex = 0;
            for(int j = 1;j < input.size() - i;j ++){
                if(comparator.compare(input.get(j),swapTarget) > 0){
                    swapTarget = input.get(j);
                    swapIndex = j;
                }
            }
            Collections.swap(input,swapIndex,input.size() - i - 1);
        }

    }


    //3. 插入排序

    /**
     * 比较次数 (1+N)N/2,移动次数可以根据暂存法优化
     *
     */
    public static <T>void insertSort(List<T> input,Comparator<T> comparator){

        for(int i = 1; i < input.size(); i ++){

            T toCompare = input.get(i);
            int newIndex = i;
            for(int j = i - 1;j >= 0; j --){

                //写法一，直接换
                /*if(comparator.compare(input.get(j),input.get(j - 1)) < 0){
                    Collections.swap(input,j,j - 1);
                    continue;
                }
                break;*/

                //写法二，存起来换
                if(comparator.compare(toCompare,input.get(j)) < 0){
                    newIndex = j;
                    /*if(j == 0){
                        moveTo(input,i,0);
                    }*/
                    continue;
                }else{
                    //moveTo(input,i,j + 1);
                    break;
                }
            }
            moveTo(input,i,newIndex,1);
        }

    }

    private static <T> void moveTo(List<T> input, int formerIndex, int newIndex,int gap) {
        if(formerIndex == newIndex){
            return;
        }
        T formerIndexValue = input.get(formerIndex);
        if(formerIndex < newIndex){
            for(int i = formerIndex;i < newIndex; i += gap){
                input.set(i,input.get(i + gap));
            }
            input.set(newIndex,formerIndexValue);
        }
        if(formerIndex > newIndex){
            for(int i = formerIndex; i > newIndex; i -= gap){
                input.set(i,input.get(i - gap));
            }
            input.set(newIndex,formerIndexValue);
        }
    }

    /*4. 希尔排序
        希尔排序的原理是，插入排序在输入序列中逆序越少时表现得越好，且分组排序的时间远比整组排序低。
        希尔排序相对插入排序的两个优化
        a.所以采取先进行部分排序，后逐渐进行整体排序的策略。
        b.同时希尔排序的方法也印证了定理二，希尔排序在最初的几次排序中，采取了远距离排序的策略，令其有可能突破二次的限制。

        希尔排序的排序间隔称为希尔增量。希尔排序效率高低的关键就在于希尔增量序列的选取。
        需要以下原则：
        1.最开始的增量要相对较大（如果一开始的希尔增量过小，则一开始就需要针对大序列进行排序）；
        2.要在较短次数间完成整个排序（否则会进行多次增量排序，使得排序节省时间的效果不明显）；
        3.增量最好为质数，并且互为素数，这样 后面进行的排序只有非常小的概率去打乱前面的排序和做无用功（对之前排序过的重新排序）。

        常用增量：希尔增量 1,2,4,8.。。。。。。
        Hibbard增量 1,3,7,15,31
        Sedgewick增量 1,5,19,41,109.。。。。。。。 下标为偶数时，项为9*4的i次方- 9*2的i次方+1；下标为奇数时，项为4的i次方-3*2的i次方+1，最坏情形时间为N的4/3次方

        定理三 使用希尔增量时希尔排序的最坏情形为n方。
        最坏情形上界证明，每次是N方/增量，一共是N方+.....+N方/2的n次方，不会超过 2N方

        定理四 使用Hibbard增量时希尔排序的最坏情形为n的3/2次方。
        最坏情况的证明：在进行第K次排序时，第K+1和K+2排序已经完成，所以任何K+1和K+2间隔的数一定是正序，并且任何以K+1和K+2的线性组合为间隔的数也一定都是正序。
        由于 8（K）方+4K的数一定可以表示为K+1和K+2的线性组合（重要证明），因此8（K）方+4K间隔外的数一定和当前数的是正序的，所以最内层的循环（向前找逆序对）最多执行8K+4。
        因此每趟复杂度为K，整体复杂度为N*k。由于大约有一半的K小于根号N，当K小于根号N时，所有间隔结果相加为N*a*根号N,当K大于根号N时，所有间隔结果相加为N方/根号N，
        所以最终的最坏情形为N的3/2次方。
     */
    public static <T>void shellSort(List<T> input,Comparator<T> comparator){

        //使用希尔增量
        /*for(int gap = input.size()/2;gap >= 1;gap /= 2){
            shellSortInner(input,comparator,gap);
        }*/

       //使用Hibbard增量
       int gapSize = (int) 13;
       for(int gap = (int) (Math.pow(2,gapSize) - 1);gapSize > 0;){
           shellSortInner(input,comparator,gap);
           gapSize --;
           gap = (int) (Math.pow(2,gapSize) - 1);
       }


    }

    private static <T> void shellSortInner(List<T> input, Comparator<T> comparator, int gap) {
        for(int i = 0;i < gap;i ++){
            for(int j = i;j < input.size();j += gap){
                T toCompare = input.get(j);
                int newIndex = j;
                for(int k = j - gap;k >= 0; k -= gap){
                    if(comparator.compare(toCompare,input.get(k)) < 0){
                        newIndex = k;
                        continue;
                    }
                    break;
                }
                moveTo(input,j,newIndex,gap);
            }

        }
    }

    //5. 堆排序
    /**
     * 堆排序的比较次数（证明到时候看）TODO
     * 定理五：对N个互异项的随机排列进行堆排序所用比较的平均次数为2NlogN - O(NloglogN);
     *
     * 堆排序的移动次数
     * 差不多是N*logN次
     *
     */
    public static <T>void heapSort(List<T> input, Comparator<T> comparator){

        //1.使用java的堆排序,必须借助一个额外数组存排序结果
        /*PriorityQueue<T> priorityQueue = new PriorityQueue<>(comparator);
        for(T obj : input){
            priorityQueue.offer(obj);
        }
        input.clear();
        while (!priorityQueue.isEmpty()){
            input.add(priorityQueue.poll());
        }*/
        //2.使用自己的堆 进行排序，必须借助一个额外数组
        /*BinaryHeap heap = new BinaryHeap(comparator);
        for(T obj : input){
            heap.add(obj);
        }
        input.clear();
        while (heap.currentIndex > -1) {
            input.add((T) heap.poll());
        }*/

        //3.堆排序

        BinaryHeap heap = new BinaryHeap(comparator);
        for(T obj : input){
            heap.add(obj);
        }
        input.clear();
        int currentIndex = heap.currentIndex;
        while (heap.currentIndex > -1) {
            heap.sortOneByOne();
        }
        while(currentIndex>= 0){
            input.add((T) heap.array[currentIndex]);
            currentIndex --;
        }
        //通过改造堆得deleteMin（Max），来达到改造堆并排序的作用

    }

    //6. 归并排序

    /**
     * 分析，归并排序的复杂度，由
     * T(1) = 1
     * T(N) = 2T(N/2) + N
     * 推出T(N) = N + logN*N
     *
     * 优势，比较次数非常少，并且不需要输入为随机存取的
     * 劣势，移动次数较多，会使用额外线性内存空间
     * 特点，稳定
     *
     */

    //注意点1   只使用一个额外数组
    public static <T>void mergeSort(List<T> input, Comparator<T> comparator){

        List<T> tmp = new ArrayList<>(input);
        mergeSortInner(0,input.size() - 1,input,tmp,comparator);

    }

    private static <T> void mergeSortInner(int firstIndex, int lastIndex, List<T> input, List<T> tmp, Comparator<T> comparator) {

        if(firstIndex >= lastIndex){
            return;
        }

        int middleIndex = (firstIndex + lastIndex)/2;
        mergeSortInner(firstIndex,middleIndex,input,tmp,comparator);
        mergeSortInner(middleIndex + 1,lastIndex,input,tmp,comparator);

        int tmpIndex = firstIndex;
        int one = firstIndex;
        int two = middleIndex + 1;
        while(one <= middleIndex && two <= lastIndex){
            T tmp1 = input.get(one);
            T tmp2 = input.get(two);


            if (comparator.compare(tmp1, tmp2) < 0) {
                tmp.set(tmpIndex, tmp1);
                one++;
            } else {
                tmp.set(tmpIndex, tmp2);
                two++;
            }
            tmpIndex ++;
        }
        if(one <= middleIndex){
            while(one <= middleIndex) {
                tmp.set(tmpIndex++, input.get(one++));
            }
        }
        if(two <= lastIndex){
            while(two <= middleIndex) {
                tmp.set(tmpIndex++, input.get(two++));
            }
        }

        for(int i = firstIndex;i <= lastIndex; i ++){
            input.set(i,tmp.get(i));
        }

    }

    //7. 快速排序，注意点见例程

    /**
     * 快速排序递推式
     * T(N) = T(i) + T(N - i - 1) + N
     *
     * 最坏情况，显然是N方
     * 最好情况 N*logN
     * 以上可以根据递推式推出。
     *
     * 平均情况分析
     * 假设T(x)中每个x出现的几率为1/N，
     * T = T(1) +...+T(X)
     * 所以 T(N) = 2 * T/N  + N
     * 再表示出T(N - 1) = 2 * (T - T(N)) / N - 1   + N - 1
     *
     * 由此逐步递推出T(N)/(N + 1) = T(1)/2 + 2c(3 + .... + N+1)
     *
     *
     * 枢纽元选择技巧 TODO
     *
     */
    public static <T>void quickSort(List<T> input, Comparator<T> comparator){
        quickSortInner(0,input.size() - 1,input,comparator);
    }
    private static <T> void quickSortInner(int start, int end, List<T> input, Comparator<T> comparator) {

        if(start >= end){
            return;
        }
        if(end - start <= 20){
            //插入排序，数组长度比较少时，使用插入排序。
        }
        int ascIndex = doThisRoundQuickSort(start, end, input, comparator);

        quickSortInner(start,ascIndex - 1,input,comparator);
        quickSortInner(ascIndex + 1 ,end,input,comparator);



    }

    public static <T> int doThisRoundQuickSort(int start, int end, List<T> input, Comparator<T> comparator) {
        //注意点1，枢纽元的选择，越靠近中值效率越高，采取三数中值分割法。
        T standard = null;
        int middleIndex = (start + end)/2;
        T first = input.get(start);
        T second = input.get(middleIndex);
        T third = input.get(end);
        int index = 0;
        if(comparator.compare(first,second) < 0){
            if(comparator.compare(second,third) < 0){
                standard = second;
                index = middleIndex;
            }else if(comparator.compare(first,third) < 0){
                standard = third;
                index = end;
            }else{
                standard = first;
                index = start;
            }
        }else{
            if(comparator.compare(first,third) < 0){
                standard = first;
                index = start;
            }else if( comparator.compare(second,third) < 0){
                standard = third;
                index = end;
            }else{
                standard = second;
                index = middleIndex;
            }
        }

        //注意点2，分割递归内容时，容易低效，甚至死循环，最佳模式是将枢纽元排除在外，这样至少不会死循环。
        //把枢纽元放在最右边
        Collections.swap(input,end,index);
        int ascIndex = start - 1;
        int descIndex = end ;
        while(ascIndex <= descIndex){
            while(ascIndex <= descIndex) {
                //注意点三，等于的处理，枢纽元时也停止，避免大量相同元素而产生非常长的子数组问题

                //注意点四，index进击的问题。由于三的存在，如果在等于的时候停止，但却不改变指针，则有可能出现死循环。所以每次停止index都++是正确的选择。
                if(ascIndex < end) {
                    if (comparator.compare(input.get(++ascIndex), standard) >= 0) {
                        break;
                    }
                }
            }

            while(descIndex >= ascIndex){
                if(descIndex > 0) {
                    if (comparator.compare(input.get(--descIndex), standard) <= 0) {
                        break;
                    }
                }

            }
            if(ascIndex <= descIndex) {
                Collections.swap(input, ascIndex, descIndex);
            }
        }

        //if(descIndex < ascIndex){
        //descIndex ++;

        //正向越界，因为反向的指针指向处一定符合反向条件，正向一定会在这里break；除了第一回合。

        //反向最后有可能越界，如果反向越界，descIndex++。

        //不管如何，正向最终一定会留在反向指标的右边一个，且他的左边都小于枢纽元，反向指标的右边都大于枢纽元
        //将枢纽元与正向指标交换
        Collections.swap(input,ascIndex,end);
        return ascIndex;
    }

    /**
     * 8.归并排序和快速排序的比较。
     * 归并排序是稳定排序，快速排序是非稳定排序。
     * 归并排序需要额外空间，快速排序不需要。
     * 归并排序每轮比较N次，一共logN轮。快速排序每轮比较N+a次，a为枢纽元选取的比较值。一共logN轮。归并排序的比较次数相对来说是最少的
     * 归并排序一共移动2N*logN次。快速排序一共移动3/2*N*logN次。
     * 归并排序实际上只需要顺序访问数据，所以在一些外部排序中得到运用。
     *
     *
     */




    //9.排序时间下界证明。

    /**
     * 引入决策树
     * 决策树的树根包含了待解决问题的所有可能，在排序问题中，就是所有可能的排序。
     * 决策树的每向下一个深度，代表着一项决策，这项决策的结果有多个，每个能够排除一些可能。在基于比较的排序问题中，决策就是比较，它的各个结构都能够排除一些顺序可能。
     *决策树的每个叶子代表一种结果
     *
     * 显然，不同的决策策略（算法），会导致决策个数的不同，也因此会有不同的决策树。
     *
     * 所谓算法的最坏情形的复杂度就是
     * 该决策树中最深的那一个分支的深度
     *
     * 平均情形就是
     * 该决策树中每个分支的平均深度。
     *
     * 最好情形就是
     * 该决策树中最浅分支的深度
     *
     *
     * 所有算法最坏情形的最好情形，就是所有算法的最坏情形中最佳的那个。
     * 所有算法平均情形的最好情形。。。。。
     * 所有算法最佳情形的最好情形。。。。。
     *
     *             。。。最坏情形
     *             。。。最坏情形
     *             。。。最坏情形
     *
     *
     * 定理7.6 所有基于比较的排序算法在其最坏情形下，最好也要比较log(N!)次。
     *
     * 定理7.7 所有基于比较的排序算法在其最坏情形下，最好也要比较N logN 次。
     *
     * 所有基于比较的排序算法在其平均情形下，最好也要比较N* logN次。
     *
     * 决策树下界是一个松下界，并不是一个紧下界。较好的算法和较弱的算法往往看不出来。
     *
     * 注意，对于一颗决策树，每一个叶子的意义为，每一个可能出现的情况。
     * 每一条从根到某一个叶子的路径，就是该可能的情况对应的有意义的情况如果为真实情况，则用该算法所需要的步骤。
     *
     */

    //选择问题的决策树下界

    /**
     *选择问题的可能的结果数量比排序问题要小。
     * 排序问题的所有可能情况数量为N!，其有意义的情况数量也为N!
     * 而选择问题的可能情况数量为N!，其有意义的情况数量为？（暂时没有想象出来，只能用  选最小的情况时，至少比较n-1次，来计算出有意义的情形为2（n-1）次方）
     * 选择问题选择第k个大小的情形的数量为  从k到最后的数中选择最小的 的情形数量 *  从1到k-1的情形数量。因此选择第k个大小的最坏情形的下界为 A（k-1 N）*2(n-k)次方。
     *
     * 基本上需要 log （A（k-1 N）*2(n-k)次方） 次。
     *
     * 定理 7.8 任何基于比较的算法，找最小元至少用N-1次比较。
     *
     * 定理7.9 任何基于比较找第k小元的算法必须至少用N-k+log(N k-1)次比较
     *
     * 定理7.10 任何基于比较找第二小元的算法必须至少用N+ logN - 2次比较
     *
     * 定理7.11 任何基于比较找中位数的算法必须至少用3N/2 - O(logN)次比较。
     *
     *
     *
     *
     */


    //10.对手下界

    /**
     * 对手下界的基本思路
     *
     * 1.找到问题解决所需要的信息数
     * 2.对手模拟操作，计算每一次模拟的操作能够给出多少信息数。
     * 3.算出至少需要操作多少次。
     *
     *
     * 决策树下界很容易算出一个非常松的下界，而对手下界相对而言可以产生比较紧的下界。
     *
     *
     *
     */


    //11.桶排序

    /**
     * 桶排序的前提：排序的对象可以由排序值来表示，且排序值的大小在已知的范围内
     * 桶排序的复杂度：时间O(M+N)空间O(M) m为范围，N为排序个数。
     *
     * 应用场景，已知排序数的范围，且范围不是特别大的情况下。等级排行等。
     *
     * @param input
     * @param start
     * @param end
     */
    public static void bucketSort(List<Integer> input,int start, int end){

        if(start > end){
            return;
        }

        int[] tmp = new int[end - start + 1];

        int offset = start;

        for(Integer i : input){
            if(start > i || end < i){
                System.out.println("不符合范围要求");
                return;
            }
            tmp[i - offset] += 1;
        }

        input.clear();
        //System.out.println(Arrays.toString(tmp));
        for(int i = 0; i < tmp.length;i ++){
            //tmp[i] -- 会改数组对象中的值。foreach遍历，改其中的i并不会改数组对象中的值
            while(tmp[i] -- > 0){
                input.add(i);
            }
        }
        //System.out.println(Arrays.toString(tmp));

    }

    /**
     *
     *
     */

    //12.基数排序 与 计数基数排序

    /**
     * 基数排序
     * 如果给定输入值的范围非常大，则桶排序将占用非常大的空间。
     * 为此，将输入范围进行拆分。每一趟按照一个进位内的数进行桶排序。
     * 如范围为0- 99999，则先进行个位的桶排序，每个桶排序需要10个桶，将会排序5次。
     * 这样就使得空间复杂度缩减为常数10，而时间复杂度则为O(p(N + b)),其中b为每趟桶数，p为位数。
     *
     * 如果排序的数值的范围大于等于待排序个数p倍，则基数排序完全优于同条件下桶排序。
     * 实践中基数排序在时间上只有在范围大于个数很多的时候才会有对桶排序有优势，但是内存的优势是明显的。
     *
     * 基数排序常被用来做字符串排序，因为字符串的范围常常比较大（26进制），利用基数排序将字符范围和字符数量分割，即可以做小容量优先次数的桶排序。
     *
     * @param input
     * @param start
     * @param end
     */
    public static void radixSort(List<Integer> input,int start, int end){

        int allRange = end - start;
        int filter = 10;

        int offset = start;
        List<Integer>[] tmp = new List[10];

        while(allRange > 0){

            int tmpFilter = filter/10;
            for(Integer i : input){
                int value = ((i - offset)%filter)/(tmpFilter);
                if(tmp[value] == null){
                    tmp[value] = new ArrayList<>();
                }
                tmp[value].add(i);
            }
            //显然这里的处理是有问题的，因为根本没必要全部都逐出，进行修改即可，浪费空间。
            input.clear();

            for(int i = 0;i < tmp.length;i ++){

                List<Integer> arrayList = tmp[i];
                while(arrayList.size() > 0){
                    input.add(arrayList.get(arrayList.size() - 1));
                    arrayList.remove(arrayList.size() - 1);
                }
            }

            filter *= 10;
            allRange /= 10;
        }
    }

    public static void countRadixSort(List<Integer> in,int start, int end){

        List<Integer> output = new ArrayList<>(in);
        List<Integer> input = in;
        int[] countInfo = new int[11];
        int filter = 10;

        int allRange = end - start;
        int tmpFilter = filter;

        int offset = start;
        int times = 0;

        while(allRange > 0) {

            int thisFilter = tmpFilter / filter;

            for (int i = 0; i < input.size(); i++) {
                int value = input.get(i);
                int index = (value % tmpFilter)/thisFilter;
                countInfo[index + 1] ++;
            }

            for(int i = 1;i < countInfo.length;i ++){
                countInfo[i] += countInfo[i - 1];
            }

            for(int i = 0;i < input.size(); i ++){

                int value = input.get(i);
                int index = (value % tmpFilter)/thisFilter;

                output.set(countInfo[index] ++,value);

            }

            List tmp = input;
            input = output;
            output = tmp;

            for(int i = 0; i < countInfo.length;i ++){
                countInfo[i] = 0;
            }

            allRange /= filter;
            tmpFilter *= filter;
            times ++;
        }

        if(times % 1 == 0){
            for(int i = 0;i < in.size();i ++){
                in.set(i,input.get(i));
            }
        }else{
            for(int i = 0;i < in.size();i ++){
                in.set(i,output.get(i));
            }
        }

    }

    //13.位图

    //14.外部排序

    //15.java使用的排序

    public static void main(String[] args){

        MultiThreadSort multiThreadSort = new MultiThreadSort();
        multiThreadSort.init();

        int count = 10000000;
        int range = 100000000;

        int sortTimes = 1;

        Random random = new Random();
        List<Integer> list = new ArrayList<>();

        for(int i = 0; i < count; i ++) {
            list.add(random.nextInt(range));
            //list.add(range - i);
            //list.add(2 - i%2);
        }
        //list.add(random.nextInt(range));

        Comparator comparator =  Comparator.naturalOrder();

        long before = System.currentTimeMillis();
        System.out.println(before);
        while(sortTimes -- > 0){
            //bubbleSort(list,comparator);
            //selectSort(list,comparator);
            //insertSort(list,comparator);
            //shellSort(list,comparator);
            //heapSort(list,comparator);
            //mergeSort(list,comparator);
            //quickSort(list,comparator);
            //multiThreadSort.quickSort(0,list.size() - 1,list,comparator);
            //Collections.sort(list,comparator);
            //Collections.shuffle(list);
            //bucketSort(list,0,range);
            //radixSort(list,0,range);
            //countRadixSort(list,0,range);
        }

        long after = System.currentTimeMillis();


        //System.out.println(list);
        System.out.println(after - before);

    }

}
